package com.cb2.algorithm.leetcode;

/**
 * <a href="https://leetcode.cn/problems/reverse-linked-list-ii">反转链表 II(Reverse Linked List II)</a>
 * <p>给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。 </p>
 * <p>
 * <b>示例</b>
 * <pre>
 * 示例 1：
 *      输入：head = [1,2,3,4,5], left = 2, right = 4
 *      输出：[1,4,3,2,5]
 *
 * 示例 2：
 *      输入：head = [5], left = 1, right = 1
 *      输出：[5]
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 *     <ul>
 *          <li>链表中节点数目为 n</li>
 *          <li>1 <= n <= 500</li>
 *          <li>-500 <= Node.val <= 500</li>
 *          <li>1 <= left <= right <= n</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/10/13 11:21
 */
public class LC0092ReverseLinkedList_II_M {

    static class Solution {
        /**
         * 思路：找到left节点的前一个节点，对后续的节点进行反转
         */
        public ListNode reverseBetween(ListNode head, int left, int right) {
            ListNode dummy = new ListNode(-1, head);
            // 找到left所在位置的前一个节点
            ListNode prevNode = dummy;
            for (int i = 0; i < left - 1; i++) {
                prevNode = prevNode.next;
            }
            ListNode currNode = prevNode.next;
            ListNode nextNode;
            for (int i = left; i < right; i++) {
                nextNode = currNode.next;
                currNode.next = nextNode.next;
                nextNode.next = prevNode.next;
                prevNode.next = nextNode;
            }
            return dummy.next;
        }


        /**
         * 思路：先断开，再反转，再拼接
         */
        public ListNode reverseBetween2(ListNode head, int left, int right) {
            // 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论
            ListNode dummyNode = new ListNode(-1, head);
            // 从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点。记为第一段链表的尾
            ListNode firstTail = dummyNode;
            for (int i = 0; i < left - 1; i++) {
                firstTail = firstTail.next;
            }
            // 第一段链表的尾的下一个节点，即要反转链表的头。
            ListNode targetHead = firstTail.next;
            firstTail.next = null;  //  断开链表

            // 从 targetHead 走 right - left步，来到第二段节点的头节点的前一个节点，即要反转链表的尾节点
            ListNode targetTail = targetHead;
            for (int i = left; i < right; i++) {
                targetTail = targetTail.next;
            }

            // 记录第二段链表的头节点，并与目标链表断开
            ListNode secondHead = targetTail.next;
            targetTail.next = null;

            // 反转目标链表
            ListNode prevNode = null;
            ListNode currNode = targetHead;
            ListNode nextNode;
            while (currNode != null) {
                nextNode = currNode.next;
                currNode.next = prevNode;
                prevNode = currNode;
                currNode = nextNode;
            }

            // 返回后：目标链表头变成尾，尾变成头
            firstTail.next = targetTail;
            targetHead.next = secondHead;
            return dummyNode.next;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        Printer.printListNode(solution.reverseBetween(Generator.create(1, 2, 3, 4, 5), 2, 4));
        Printer.printListNode(solution.reverseBetween(Generator.create(5), 1, 1));
    }
}